#!/usr/bin/env python3

"""
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n)
"""


class Solution:
    def min_window(self, s, t):
        if len(s) == 0 or len(t) == 0:
            return ""

        start = end = None
        left = right = 0
        need = {}
        for t_ch in t:
            if t_ch in need:
                need[t_ch] = need[t_ch] + 1
            else:
                need[t_ch] = 1
        container = {key: 0 for key in need}
        missing = len(t)
        while right < len(s):
            right_val = s[right]
            if right_val not in need:
                right += 1
                continue
            container[right_val] += 1
            if container[right_val] <= need[right_val]:
                missing -= 1
                if missing == 0:
                    while left <= right:
                        left_val = s[left]
                        left += 1
                        if left_val in need:
                            container[left_val] -= 1
                            if container[left_val] == need[left_val] - 1:
                                if start is None or (right - left + 1) < (end - start):
                                    start = left - 1
                                    end = right
                                missing += 1
                                break
            right += 1
        if start is None:
            return ""
        return s[start: end + 1]
                
if __name__ == '__main__':
    s = Solution()
    assert "BANC" == s.min_window("ADOBECODEBANC", "ABC")
